/**
 * 顺序表模板
 */
#include <iostream>

using namespace std;

#define eleType int // 宏定义一个顺序表数据类型

struct SequenceList
{
    eleType *pElements; // 顺序表里面的元素类型
    int nSize;          // 数量
    int nCapacity;      // 容量
};

/**
 * 初始化顺序表
 */
void initializeList(SequenceList *pList, int nCapacity)
{
    pList->pElements = new eleType[nCapacity]; // 创建一个空顺序表，容量大小为nCapacity个eleType(数据类型)
    pList->nSize = 0;                          // 数量为0
    pList->nCapacity = nCapacity;              // 容量大小为nCapacity
}

/**
 * 销毁顺序表
 */
void destroyList(SequenceList *pList)
{
    delete[] pList->pElements; // 删除顺序表的容量
}

/**
 * 获取顺序表的大小
 */
int getListSize(SequenceList *pList)
{
    return pList->nSize;
}

/**
 * 判断顺序表大小是否为0
 */
bool isEmpty(SequenceList *pList)
{
    return pList->nSize == 0;
}

/**
 * 插入***
 */
void insertList(SequenceList *pList, int nIndex, eleType element)
{
    // 1、判断插入位置是否正确
    if (nIndex < 0 || nIndex > pList->nSize)
    {
        throw std::invalid_argument("Invalid nIndex");
    }
    // 2、判断容量是否可以进行插入
    if (pList->nCapacity == pList->nSize)
    {
        // 3、扩容
        int nNewCapacity = pList->nCapacity * 2;
        // 申请一个更大的空间
        eleType *newElements = new eleType[nNewCapacity];
        // 将之前的数据拷贝到当前的新空间
        for (int i = 0; i < pList->nSize; ++i)
        {
            newElements[i] = pList->pElements[i];
        }
        // 销毁原来的空间
        delete[] pList->pElements;
        // 新链表
        pList->pElements = newElements; 
        pList->nCapacity = nNewCapacity;
    }
    // 3、新元素插入（从后往前）
    for (int i = pList->nSize; i > nIndex; --i)
    {
        pList->pElements[i] = pList->pElements[i - 1];
    }
    pList->pElements[nIndex] = element;
    pList->nSize++;
}

/**
 * 删除
 */
void deleteElement(SequenceList *pList, int nIndex)
{
    // 1、判断删除位置是否正确
    if (nIndex < 0 || nIndex >= pList->nSize)
    {
        throw std::invalid_argument("Invalid nIndex");
    }
    // 2、删除（从前往后，要删除的位置开始，到最后一个）
    for (int i = nIndex; i < pList->nSize; ++i)
    {
        pList->pElements[i] = pList->pElements[i + 1];
    }
    pList->nSize--;
}

/**
 * 查找（返回下标值）
 */
int findElement(SequenceList *pList, eleType element)
{
    for (int i = 0; i < pList->nSize; ++i)
    {
        if (pList->pElements[i] == element)
            return i;
    }
    return -1;
}

/**
 * 索引
 */
eleType getElement(SequenceList *pList, int nIndex)
{
    if (nIndex < 0 || nIndex >= pList->nSize)
    {
        throw std::invalid_argument("Invalid nIndex");
    }
    return pList->pElements[nIndex];
}

/**
 * 修改
 */
void updateElement(SequenceList *pList, int nIndex, eleType element)
{
    if (nIndex < 0 || nIndex >= pList->nSize)
    {
        throw std::invalid_argument("Invalid nIndex");
    }
    pList->pElements[nIndex] = element;
}

int main()
{
    // 测试
    SequenceList myList;
    initializeList(&myList, 10);
    for (int i = 0; i < 10; ++i)
    {
        // 插入操作
        insertList(&myList, i, i * 10);
    }
    cout << "List Size:" << getListSize(&myList) << endl;
    cout << "List is Empty:" << isEmpty(&myList) << endl;
    for (int i = 0; i < myList.nSize; ++i)
    {
        cout << myList.pElements[i] << " ";
    }
    cout << endl;

    // 插入扩容测试
    insertList(&myList, 5, 120);
    cout << "List Size:" << getListSize(&myList) << endl;
    for (int i = 0; i < getListSize(&myList); ++i)
    {
        cout << getElement(&myList, i) << " ";
    }
    cout << endl;

    // 删除
    deleteElement(&myList, 3);
    cout << "删除脚标为3的值:";
    for (int i = 0; i < getListSize(&myList); ++i)
    {
        cout << getElement(&myList, i) << " ";
    }
    cout << endl;

    // 查找
    cout << "查找20的脚标：" << findElement(&myList, 20) << endl;

    // 修改
    updateElement(&myList, 6, 10000);
    for (int i = 0; i < getListSize(&myList); ++i)
    {
        cout << getElement(&myList, i) << " ";
    }
    cout << endl;
    
    return 0; 
}